#47. 全排列 II

LeetCode 原题链接

#题目描述

给定一个可能包含重复数字的数组 nums，按任意顺序返回所有不重复的全排列。

输入：nums = [1,1,2]
输出：[[1,1,2], [1,2,1], [2,1,1]]

#题型判断

排列需要依次确定每一个位置放哪个数字。每一层递归选择一个当前尚未使用的元素，进入下一层；路径长度等于数组长度时得到一个完整排列，因此主体仍然是回溯：

做选择 → 递归 → 撤销选择

本题比普通全排列多了重复元素。如果只使用 used 数组，能够避免同一个下标被重复选择，却不能避免值相同的元素在同一层产生等价分支。

例如 nums = [1a,1b,2]，首层先选 1a 和先选 1b，最终产生的排列完全相同。真正需要解决的是：

同一树枝上的重复值可以使用，同一树层上的重复值只能选择一次。

#核心思路：排序 + 回溯 + 同层去重

先对数组排序，让值相同的元素相邻，然后维护：

• path：当前已经确定的排列前缀；
• used[i]：下标 i 的元素是否已经在当前路径中；
• result：所有已经完成的不重复排列。

每层都从下标 0 开始枚举，因为排列中的后一个位置仍然可以选择数组前面的元素。候选元素需要通过两个判断：

if (used[i]) continue;

if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
  continue;
}

两个判断分别解决不同问题：

1. used[i] 为 true：当前下标已经在本条路径中使用，不能再次使用。
2. 当前值等于前一个值，并且前一个值没有在当前路径中使用：说明它们是当前树层的两个等价选择，应跳过后一个。

#为什么去重条件是 !used[i - 1]

这是本题最关键的一行：

i > 0 && nums[i] === nums[i - 1] && !used[i - 1]

可以分两种情况理解。

#情况一：used[i - 1] === false

前一个相同元素没有出现在当前路径中。由于数组已经排序，它通常意味着前一个相同元素已经在当前层被选择、递归并撤销了。

此时再选择当前元素，会生成完全相同的子树，所以必须跳过：

[]
├─ 选择 1a：会生成 [1,1,2]、[1,2,1]
└─ 选择 1b：还会生成 [1,1,2]、[1,2,1]  ← 重复，剪枝

#情况二：used[i - 1] === true

前一个相同元素已经在更高层的当前路径中使用。此时选择当前元素，是在同一条树枝上使用数组中的另一个重复元素，是合法的。

例如生成 [1,1,2] 时：

第一层选择第一个 1
第二层选择第二个 1
第三层选择 2

因此不能看到相邻元素相同就一律跳过，还必须结合 used[i - 1] 判断它属于“同层”还是“同一条路径”。

#示例推演

排序后的数组仍为 [1a,1b,2]，字母只用来区分相同数字的不同下标：

[]
├─ 1a
│  ├─ 1b
│  │  └─ 2       => [1,1,2]
│  └─ 2
│     └─ 1b      => [1,2,1]
├─ 1b             => 与首层选择 1a 等价，跳过
└─ 2
   ├─ 1a
   │  └─ 1b      => [2,1,1]
   └─ 1b          => 与本层选择 1a 等价，跳过

注意这里剪掉的只是同一层中的等价分支，不会剪掉 [1,1,2] 中第二个合法的 1。

#JavaScript 实现

var permuteUnique = function (nums) {
  nums.sort((a, b) => a - b);

  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);

  const backtrack = () => {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      // 同一个下标不能在当前排列中使用两次
      if (used[i]) continue;

      // 同一树层中，相同的值只能作为候选一次
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
        continue;
      }

      path.push(nums[i]);
      used[i] = true;

      backtrack();

      used[i] = false;
      path.pop();
    }
  };

  backtrack();
  return result;
};

#代码执行过程

以 nums = [1,1,2] 为例：

每次递归入口都保持以下不变量：

used[i] 为 true，当且仅当下标 i 的元素已经出现在当前 path 中。

回溯返回父层前必须同时恢复 path 和 used，否则这个对应关系会被破坏。

#正确性说明

算法不会漏解：对于任意合法排列，从左到右依次选择它的元素，都能在搜索树中找到对应路径。同一条路径允许选择多个值相同但下标不同的元素，因此重复数字不会被错误删除。

算法不会产生重复解：排序后，相同元素相邻。在同一递归层中，只允许最靠前且当前可用的相同元素建立分支，其他相同元素对应的等价子树都会被剪掉。因此每一种不同排列只会被生成一次。

#复杂度分析

• 排序时间复杂度：O(n log n)。
• 回溯时间复杂度：最坏为 O(n × n!)。最多有 n! 个排列，保存每个排列副本需要 O(n)。
• 辅助空间复杂度：O(n)，包括递归栈、path 和 used；不计算返回结果。
• 结果空间复杂度：最坏为 O(n × n!)。

存在重复元素时，实际排列数量为：

n! / (c1! × c2! × ... × ck!)

其中 c1、c2、...、ck 是各个不同数字出现的次数。

#常见错误

#1. 只使用 used，没有同层去重

if (used[i]) continue;

这只能防止重复使用同一个下标，无法避免两个值相同的下标生成相同排列。

#2. 去重前没有排序

if (nums[i] === nums[i - 1]) {
  // ...
}

相邻比较依赖重复值已经聚集在一起，因此必须先排序。

#3. 无条件跳过相邻的重复值

if (i > 0 && nums[i] === nums[i - 1]) continue;

这会同时禁止同一条路径使用两个重复数字，导致 [1,1,2] 这样的合法答案被漏掉。

#4. 忘记复制路径

result.push(path); // 错误：保存的是同一个数组引用

应该保存当前路径的副本：

result.push([...path]);

#5. 使用 startIndex

startIndex 适合组合和子集，因为它们只关心选择了哪些元素；排列还关心顺序，每一层都要从整个数组中寻找尚未使用的元素。

#另一种写法：按数字频次回溯

也可以先统计每个数字的出现次数。每次选择某个数字后将频次减一，回溯时再恢复。这种写法天然以“值”为单位，不会创建值相同的重复分支。

var permuteUnique = function (nums) {
  const count = new Map();
  for (const num of nums) {
    count.set(num, (count.get(num) ?? 0) + 1);
  }

  const result = [];
  const path = [];

  const backtrack = () => {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (const [num, frequency] of count) {
      if (frequency === 0) continue;

      path.push(num);
      count.set(num, frequency - 1);

      backtrack();

      count.set(num, frequency);
      path.pop();
    }
  };

  backtrack();
  return result;
};

排序加 used 是更常见的面试写法，能够清楚展示“树层去重”；频次写法则更直接地表达“每个值还剩多少个可用”。

#与普通全排列的区别

可以把本题记成普通全排列模板加上一条规则：

if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;

但面试时不能只背这一行，还要能解释：!used[i - 1] 表示前一个相同元素不在当前路径中，因此当前元素属于同一树层的重复选择。

#自测问题

1. used[i] 和同层去重判断分别解决什么问题？
2. 为什么排序是相邻去重的前提？
3. 为什么条件使用 !used[i - 1]，而不是 used[i - 1]？
4. 为什么排列问题的每一层都从下标 0 开始枚举？
5. 如果不允许修改输入数组，应该如何调整排序代码？

第 5 题可以使用副本：

const sortedNums = [...nums].sort((a, b) => a - b);